/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package shortestpath;

import java.lang.String;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;
import entity.Cell;
import model.Arena;
import model.Robot;


/**
 *
 * @author Anh
 */

public class MinRotation {     
    public static final int WIDTH = 20;
    public static final int HEIGHT = 15;
    
    public static final int dx[] = {0, 1, 0, -1};
    public static final int dy[] = {-1, 0 , 1, 0};
    
    public static boolean free[][];
    public static Cell prev[][][];
    public static int prevDir[][][];
    public static int dist[][][];
    public static boolean map[][];
    
    public static final int MAXN = 40;
    
        
    public static int getDirection(Cell start, Cell finish) {
        for (int dir = 0; dir < 4; dir ++)
            if (  dx[dir] == finish.x - start.x 
               && dy[dir] == finish.y - start.y) return dir;
        return -1;
    }
    
    public static void initArray() {
        free = new boolean[MAXN][];
        for (int i = 0; i < MAXN; i++)
            free[i]= new boolean[MAXN];
        
        prev = new Cell[MAXN][][];
        for (int i = 0; i < MAXN; i++)
            prev[i] = new Cell[MAXN][];
        for (int i = 0; i < MAXN; i++)
            for (int j = 0; j < MAXN; j++)
                prev[i][j] = new Cell[4];
        
        prevDir = new int[MAXN][][];
        for (int i = 0; i < MAXN; i++)
            prevDir[i] = new int[MAXN][];
        for (int i = 0; i < MAXN; i++)
            for (int j = 0; j < MAXN; j++)
                prevDir[i][j] = new int[4];
        
        
        dist = new int[MAXN][][];
        for (int i = 0; i < MAXN; i++)
            dist[i] = new int[MAXN][];
        for (int i = 0; i < MAXN; i++)
            for (int j = 0; j < MAXN; j++)
                dist[i][j] = new int[10];
        
        map = new boolean[MAXN][];
        for (int i = 0; i < MAXN; i++)
            map[i] = new boolean[MAXN];
    }
    
    public static boolean inside(Cell c) {
        return (0 <= c.x && c.x < WIDTH && 0 <= c.y && c.y < HEIGHT);
    }
    
    public static Vector<String> BFS() {
        
        initArray();
        
        for (int x = 0; x < WIDTH; x++)
            for (int y = 0; y < HEIGHT; y++) {
                map[x][y] = Arena.getInstance().isEmptyCell(new Cell(x, y));
                //map[x][y] = (x - y <= 10);
            }
        
        
     for (int y = 0; y < HEIGHT; y++) {
            for (int x = 0; x < WIDTH; x++)        
                if (map[x][y]) System.out.print(0);
                        else System.out.print(1);
                System.out.println();
        }     
        
        for (int i = 0; i < MAXN; i++)
            for (int j = 0; j < MAXN; j++)
                free[i][j] = true;
        
        for (int x = 0; x < WIDTH; x++) 
            for (int y = 0; y < HEIGHT; y++)
                for (int d = 0; d < 4; d++)
                    dist[x][y][d] = 100;
        
        for (int x = 0; x < WIDTH; x++)
            for (int y = 0; y < HEIGHT; y++) {
                boolean ok = true;
                for (int i = -1; i <= 1; i++)
                    for (int j = -1; j <= 1; j++) {
                        if (!inside(new Cell(x + i, y + j)) || 
                                !map[x + i][y + j]) ok = false;
                    }
                
                free[x][y] = ok;
            }
        
     for (int y = 0; y < HEIGHT; y++) {
            for (int x = 0; x < WIDTH; x++)        
                if (free[x][y]) System.out.print(0);
                        else System.out.print(1);
                System.out.println();
        }

        
        Queue <Cell> q = new LinkedList<Cell>();
        Queue <Integer> dirQ = new LinkedList<Integer>();
        
        int finishDir = -1;
        Cell finish = new Cell(-1, -1);
        Cell start  = new Cell(1, 1);
        
        dist[start.x][start.y][1] = 0;
        dirQ.add(1);
        q.add(start);
        
        int best = 100;
        while (!q.isEmpty()) {
            Cell u = new Cell(q.peek());
            int curDir = dirQ.peek();
            
            q.remove();
            dirQ.remove();
            //System.out.println(u.x + " " + u.y + " " + curDir);
            
            for (int d = 0; d < 4; d++) {
                Cell v = new Cell(u);
                
                v.x += dx[d];
                v.y += dy[d];
                
                int cnt = (d - curDir);
                if (cnt < 0) cnt = - cnt;
                
                if (inside(v) && free[v.x][v.y] && dist[v.x][v.y][d] > dist[u.x][u.y][curDir] + cnt) {
                    dist[v.x][v.y][d] = dist[u.x][u.y][curDir] + cnt;
                    
                    q.add(v);
                    dirQ.add(d);
                    
                    prev[v.x][v.y][d] = new Cell(u);
                    prevDir[v.x][v.y][d] = curDir;
                    
                    //System.out.print(v.x + " " + v.y + ": ");
                    //System.out.println(u.x + " " + u.y);
                    //System.out.println(prev[v.x][v.y].x + " " + prev[v.x][v.y].y);
                    
                    if (v.x >= WIDTH - 2 && v.y >= HEIGHT - 2 && best < dist[v.x][v.y][d]) {
                        best = dist[v.x][v.y][d];
                        finish = new Cell(v);
                        finishDir = d;
                    }
                }
            }
            
        }
        
        Vector<String> path = new Vector<String>();
        Vector<Cell> cells = new Vector<Cell>();
        
        //System.out.println(finish.x + " " + finish.y);
        while (true) {
            cells.add(finish);
            if (finish.isEqual(start)) break;
            int tmp = finishDir;
            finishDir = prevDir[finish.x][finish.y][finishDir];
            finish = prev[finish.x][finish.y][tmp];
            
            //Cell u = prev[finish.x][finish.y];
        }
       
        /*
        for (int i = cells.size()- 1; i >= 0; i--) {
            System.out.println(cells.get(i).x + " " + cells.get(i).y);
        }
        * */
        
        int direction = 1;
        for (int i = cells.size() - 1; i > 0; i--) {
            int dir = getDirection(cells.get(i), cells.get(i - 1));
            
            
            if (dir == (direction + 1) % 4) path.add("R");
            else if (dir == (direction + 2) % 4) {
                path.add("R");
                path.add("R");
            } else if (dir == (direction + 3) % 4) path.add("L");
            
            direction = dir;
            path.add("G1");
        }
        
        Vector<String> compressedPath = new Vector<String>();
        
        int cnt = 0;
        for (int i = 0; i < path.size(); i++) 
            if (path.get(i) == "G1") cnt++;
            else {
                if (cnt > 0) compressedPath.add("G" + cnt + "|");
                cnt = 0;
                compressedPath.add(path.get(i));
            }
        if (cnt > 0) compressedPath.add("G" + cnt + "|");
        
        for (int i = 0; i < compressedPath.size(); i++)
            System.out.print(compressedPath.get(i));
        return compressedPath;
    }
    
}
